package baseclass.d_list;


import utils.ListNode;
import utils.ListUtil;

import java.util.Stack;

/**
 * 【题目】 给定一个链表的头节点head， 请判断该链表是否为回文结构。
 * 例如： 1->2->1， 返回true。 1->2->2->1， 返回true。
 * <p>
 * 笔试可以用简单的：
 * 方式1：依次遍历入栈，栈弹出再一次和链表比较。
 * <p>
 * 方式2：遍历到一半，然后另一半入栈，同上都是o(N)空间复杂度
 * <p>
 * 方式3：
 * 设置两个指针，一个走一步，一个走两步。
 * 如果是奇数，慢指针落在 中间位置，入栈需要+1
 * 如果是偶数，慢指针落在 两个中间的前一个位置。入栈需要+1
 * 注意：在数组中,length/2若是奇数，则在中间，若是偶数，则在中间的前一个
 * 进阶： 如果链表长度为N， 时间复杂度达到O(N)， 额外空间复杂度达到O(1)。
 * 方式：也是设置两个指针。 把中间位置的指针指向null，后面的依次把指针倒过来，然后判断。注意最后要恢复
 */
public class Code03_IsPalindromeList_回文链表 {

    // need n extra space
    public static boolean isPalindrome1(ListNode head) {
        if (head == null || head.next == null) return true;
        Stack<Integer> stack = new Stack<>();
        ListNode p1 = head;
        while (p1 != null) {
            stack.push(p1.val);
            p1 = p1.next;
        }
        p1 = head;
        while (!stack.isEmpty()) {
            if (stack.pop() != p1.val) return false;
            p1 = p1.next;
        }
        return true;
    }

    /**
     * 方式2：时间O(n),空间O(1)
     * 遍历到链表的一半后翻转。别忘了最后翻转回去
     */
    public static boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //现在slow必定是链表中间位置，如果是偶数就是前一个。
        ListNode pre = null;
        //翻转了后半部分
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = pre;
            pre = slow;
            slow = next;
        }
        boolean res = true;
        //对链表进行前后遍历
        slow = head;
        //pre是尾巴
        fast = pre;
        while (slow != null && pre != null) {
            if (slow.val != pre.val) res = false;
            slow = slow.next;
            pre = pre.next;
        }
        //把后面的再翻转回去
        pre = null;
        while (fast != null) {
            ListNode next = fast.next;
            fast.next = pre;
            pre = fast;
            fast = next;
        }
        return res;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(2);
        head.next.next.next.next.next= new ListNode(1);

       /* System.out.println(isPalindrome1(head));
        ListUtil.printLinkedList(head);*/

        System.out.println(isPalindrome2(head));
        ListUtil.printLinkedList(head);

//		ListNode head = null;
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");
//
//		head = new ListNode(1);
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");
//
//		head = new ListNode(1);
//		head.next = new ListNode(2);
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");
//
//		head = new ListNode(1);
//		head.next = new ListNode(1);
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");
//
//		head = new ListNode(1);
//		head.next = new ListNode(2);
//		head.next.next = new ListNode(3);
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");
//
//		head = new ListNode(1);
//		head.next = new ListNode(2);
//		head.next.next = new ListNode(1);
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");
//
//		head = new ListNode(1);
//		head.next = new ListNode(2);
//		head.next.next = new ListNode(3);
//		head.next.next.next = new ListNode(1);
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");
//
//		head = new ListNode(1);
//		head.next = new ListNode(2);
//		head.next.next = new ListNode(2);
//		head.next.next.next = new ListNode(1);
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");
//
//		head = new ListNode(1);
//		head.next = new ListNode(2);
//		head.next.next = new ListNode(3);
//		head.next.next.next = new ListNode(2);
//		head.next.next.next.next = new ListNode(1);
//		printLinkedList(head);
//		System.out.print(isPalindrome1(head) + " | ");
//		System.out.print(isPalindrome2(head) + " | ");
//		System.out.println(isPalindrome3(head) + " | ");
//		printLinkedList(head);
//		System.out.println("=========================");

    }


}
